﻿// 203 逆元2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <assert.h>



using namespace std;
/*
http://oj.daimayuan.top/course/21/problem/491

给一个素数 p
，求a1,a2,…,an
关于p的逆元。

由于输出可能很大，只需要求这些逆元的异或和即可。

输入格式
一行，五个整数p,n,A,B,C
。

为了防止输入过大，a
用下面代码生成。

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main() {
    scanf("%d%d%u%u%u", &p, &n, &A, &B, &C);
    for (int i = 1; i <= n; i++)
        a[i] = rng61()%p;
}
输出格式
一个整数，表示a1,a2,…,an
这些数关于p
的逆元的异或和。如果ai=0
，我们认为逆元为0
。

样例输入
10007 1000 1 2 3
样例输出
3611
数据规模
对于所有数据，保证2≤p≤109+7,1≤n≤min(107,p−1),0≤A,B,C<232
。


*/

typedef long long ll;

int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}


unsigned int A, B, C, p, n;

const int N = 100000010;
int a[N]; ll s[N], t[N];

inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main() {
    scanf("%d%d%u%u%u", &p, &n, &A, &B, &C);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = rng61() % p;
        if (0 == a[i]) {
            a[i] = 1;
            ans ^= 1;
        }
    }
    s[0] = 1;
    for (int i = 1; i <= n; i++) s[i]=s[i - 1] * a[i] % p;
    int x, y;
    exgcd(s[n], p, x, y);  
    if (x < 0) x += p;
    t[n] = x;
    assert(s[n] * x % p == 1);
    for (int i = n; i >= 1; i--) t[i - 1] = t[i] * a[i] % p;
    for (int i = 1; i <= n; i++) {
        int v = s[i - 1] * t[i] % p;
        ans ^= v;
    }
    printf("%d\n", ans);
}
